package ua.mykola.sorting;

public class QuickSort implements Sorter {

	@Override
	public void sort(Object[] array) {
		qucikSort(array, 0, array.length - 1);
	}

	private void qucikSort(Object[] array, int start, int end) {
		if (start > end)
			return;
		int pivot = (end - start) / 2 + start;
		int newPivot = partition(array, start, end, pivot);
		qucikSort(array, start, newPivot - 1);
		qucikSort(array, newPivot + 1, end);
	}

	private int partition(Object[] array, int start, int end, int pivot) {
		swap(array, end, pivot);
		Object pivotValue = array[end];
		int newPivot = start;
		for (int i = start; i < end; i++) {
			if (((Comparable) array[i]).compareTo(pivotValue) < 0) {
				swap(array, i, newPivot);
				newPivot++;
			}
		}
		swap(array, end, newPivot);
		return newPivot;
	}

	private void swap(Object[] array, int inedx1, int index2) {
		Object temp = array[inedx1];
		array[inedx1] = array[index2];
		array[index2] = temp;
	}
}
